#核心算法

from abc import ABC, abstractmethod
from settings import logger
import tag 
import math
import operateCount as operate
#
class BaseTagReader(ABC):
    ''' define a common interface for Readers implementing collision detection protocols'''
    def __init__(self):
        pass
    #抽象方法（用`@abstractmethod`装饰）
    @abstractmethod
    def manage_collision(self, tags):#纯虚函数，子类必须实现
        pass

#第一代防碰撞算法。GenOneTagReader继承BaseTagReader
'''树形算法仿真的思路：
    标签：生成规定数量的标签，每一个标签都有一个随机64位UID号,并随机设定了标签的传输时间，随机的话才可能产生碰撞
    阅读器：每次读三位ID号或者2位ID，如果搜索的标签数量小于等于1，则没有发生碰撞，如果搜索结果大于1，则发生了碰撞
    在发生碰撞的标签基础上，继续增加3位，或者2位ID继续搜索，直到搜索结果小于等于1
'''
class GenOneTagReader(BaseTagReader):

    def __init__(self):
        super().__init__()
        #包含了阅读器在每次查询中可能使用的所有前缀组合
        #这样阅读器可以将标签分成最多8个子组
        self.PREFIX_ARR = ['000', '001', '010', '011', '100', '101', '110', '111']
        self.MAX_PREFIX = len(self.PREFIX_ARR)

    def manage_collision(self, tags):
        super().manage_collision(tags)#super是调用父类已被子类重写的函数
        return self._binary_search(tags)#在tags中寻找PREFIX_ARR

    def _get_bit_string(self, i):
        if i > (self.MAX_PREFIX-1):
            return
        else:
            return self.PREFIX_ARR[i]
    
    def _binary_search(self, tags, id=''):

        # 1 slot for this evaluation and then add on the recusive chain
        num_slots = 1
        
        if id != '':
            # Then find matching tags
            matching_tags = [t for t in tags if t.id.startswith(id)]
        else:
            matching_tags = tags
        
        # logger.debug(f"TAGS MATCHING PREFIX {id}: {matching_tags}")

        '''Transmit an ID with three numbers. If collision then manage_collision with subset'''
        '''该分支成立表示搜索到唯一标签或者没有搜索到标签(即空闲时隙)''' 
        if len(matching_tags) <= 1:
            logger.debug(f'de-collided: {matching_tags}')
            # return 1 here as we are still querying on that id.
            return 1
        
        # Need all permuations of three bits 000 001 010 011 100 101 110 111
        '''读到了多个标签，即出现了标签碰撞，出现标签碰撞时，在此基础上继续增加ID号搜索，'''
        if len(matching_tags) > 1:
            for i in range(self.MAX_PREFIX):
                #等价：tmp_id = str(id) + str(self._get_bit_string(i))
                tmp_id=f'{id}{self._get_bit_string(i)}'

                logger.debug(f"de-colliding: {matching_tags} using prefix: {tmp_id}")
                num_slots += self._binary_search(matching_tags,tmp_id)
                
        # No tags matched this id.
        return num_slots


#管理标签碰撞，模拟的阅读器
class BinaryTagReader(GenOneTagReader):

    def __init__(self):
        super().__init__()
        self.PREFIX_ARR = ['0', '1']
        self.MAX_PREFIX = len(self.PREFIX_ARR)

''' ALOHA协议中，标签需要增加随机重试机制 
    阅读器和标签之间需要进行时间同步
'''
class PureAlohaTagReader(BaseTagReader):
    def __init__(self):
        super().__init__()
        # 初始化统计量
        self.total_attempts = 0  # 总传输尝试次数（即总时隙数）
        self.success_count = 0
        self.collision_count = 0
        self.heapHandle = []

    def manage_collision(self, tags):
        super().manage_collision(tags)#super是调用父类已被子类重写的函数
        
        import heapq
        # 初始化标签的传输时间并加入事件堆
        
        for tag in tags:
            tag.generate_time()
            heapq.heappush(self.heapHandle, (tag.transmit_time, tag))
        # 事件驱动仿真循环
        while self.heapHandle:
            current_time, tag = heapq.heappop(self.heapHandle)
            if not tag.active or tag.successful:#如果失效或者已经被识别则跳过处理
                continue
                
            #检测碰撞
            colliding = [tag]
            for other_tag in tags:
                #两个标签不是同一个标签，并且都处于传输状态
                if (other_tag is not tag and (other_tag.is_transmitting and tag.is_transmitting) ):
                    colliding.append(other_tag)
            
            self.total_attempts += 1  # 每次尝试计数为1个时隙
            
            # 处理碰撞结果
            if len(colliding) == 1:  # 无碰撞
                tag.mark_success()  #标签设定为被读到
                success_count += 1
            else:  # 发生碰撞
                self.collision_count += 1
                for t in colliding:
                    if t.active and not t.successful:
                        if t.handle_collision(current_time):  # 安排重传
                            heapq.heappush(self.heapHandle, (t.transmit_time, t))
            
            # 超时终止
            #if current_time > sim_time_limit:
            #    break
        #logger.info(f"total_attempts:{self.total_attempts}")
        # 返回包含总时隙数的统计结果
        return self.total_attempts
        
class FrameSlottedAlohaTagReader(BaseTagReader):
    def __init__(self,initial_frame_size=16):
        
        super().__init__()
        self.frame_size = initial_frame_size #帧大小（包含的时隙数）
        self.total_slots = 0 #总的时隙数
        self.success_count = 0 #成功识别的统计
        self.collision_count = 0 #碰撞的统计
        self.empty_slot_count = 0#空闲时隙的统计
    
    def manage_collision(self, tags):
        super().manage_collision(tags)#super是调用父类已被子类重写的函数
        # 在帧时隙ALOHA中，我们一次处理整个帧
        # 注意：这里我们假设一次manage_collision调用处理一帧
        return self.run_frame(tags)
    
    def run_frame(self , tags):
        self.reset_stats()
        #过滤出活跃的标签
        active_tags = [tag for tag in tags if tag.active] 
        #logger.info(f"tag num:{len(tags)}")
        while active_tags:
            self.total_slots += self.frame_size
            #处理一帧数据
            active_tags = self.frame_process(active_tags)
        return self.total_slots #返回使用的总时隙数
    
    def frame_process(self , activetags):
        #处于活跃的标签选择时隙
        for tag in activetags:
            tag.select_slot(self.frame_size)

        #初始化时隙数组，将在同一个时隙的标签统计出来
        slots = [[] for _ in range(self.frame_size)]
        for tag in activetags:
            slots[tag.selected_slot].append(tag)

        #处理每个时隙
        for slot_index in range(self.frame_size):
            tags_in_slot = slots[slot_index]

            if len(tags_in_slot) == 0:  #此时隙无标签，即该时隙为空闲
                self.empty_slot_count+=1
        
            elif len(tags_in_slot) == 1:#此时隙1个标签，该时隙标签可成功识别
                #成功识别
                tag = tags_in_slot[0]
                tag.mark_success()
                self.success_count += 1
            else:                       #此时隙>1个标签，该时隙标签出现碰撞
                self.collision_count += 1 
                #for tag in tags_in_slot:
                #    tag.handle_collision()#这里有问题，标签的处理碰撞函数，只有重发的计数，并没有重新选择下一帧的时隙操作
                    #安排重传，下一帧处理
        return [tag for tag in activetags if tag.active] 

    def adjust_frame_size(self, new_size):
        """调整帧大小（时隙数量）"""
        self.frame_size = max(1, new_size)  # 确保帧大小至少为1
    
    def get_stats(self):
        """获取统计信息"""
        return {
            "total_slots": self.total_slots,
            "success_count": self.success_count,
            "collision_count": self.collision_count,
            "empty_slot_count": self.empty_slot_count,
            "efficiency": self.success_count / self.total_slots if self.total_slots > 0 else 0
        }
    
    def reset_stats(self):
        """重置统计计数器"""
        self.total_slots = 0
        self.success_count = 0
        self.collision_count = 0
        self.empty_slot_count = 0 

#低复杂度动态帧时隙Aloha防冲突算法
'''核心思想：
根据上一帧的结果（空闲时隙、成功时隙、碰撞时隙）来估计标签数量范围，选择最优的帧大小
预计算边界值和分界点并进行存储
根据空闲时隙估算标签数量
通过查表(标签数量：最优帧大小)，确定下一帧的大小
针对极端情况(无空闲时隙、无成功时隙)，使用边界值进行估算
'''   
class LC_DFSATagReader(FrameSlottedAlohaTagReader):
    def __init__(self,initial_frame_size=16):
        super().__init__()
        operate.reset_stats()
        # 预定义的帧大小序列（2的幂）
        self.FRAME_SIZES = [4, 8, 16, 32, 64, 128, 256, 512, 1024 , 2048]
        self.frame_count = 0
        # 建立帧区间分界点表[(低,高,对应帧长), ...]
        self.frame_intervals = self.generate_frame_intervals()
        # 预计算边界值
        self.border_values = self.calculate_border_values()
   
    def generate_frame_intervals(self):
        """直接给出表3区间映射,如论文Table 3"""
        # 这里区间上限为包含关系，实际可精细调整
        return [
            (3, 5, 4),
            (6, 11, 8),
            (12, 22, 16),
            (23, 44, 32),
            (45, 88, 64),
            (89, 177, 128),
            (178, 355, 256),
            (356, 712, 512),
            (713, 1423, 1024),
            (1424, 2845, 2048)
        ]
    #计算边界值    
    def calculate_border_values(self):
        """
        预计算边界值 (Border Values)
        根据论文公式(12)-(14)
        """
        border_values = {}
        
        for N in self.FRAME_SIZES:
            # 空闲边界 M_{idle}^{Border}
            temp = operate.divide(1 , N)
            border_values[(N, 'idle')] = self.solve_equation(lambda M:operate.index((1 - temp),M)- temp)
            # 成功边界 M_{Suc}^{Border}
            border_values[(N, 'success')] = self.solve_equation(lambda M:operate.multiply(operate.multiply(M , temp),operate.index((1 - temp),(M-1))) - temp)
            # 碰撞边界 M_{Coll}^{Border}
            border_values[(N, 'collision')] = self.solve_equation(lambda M:operate.index((1 - temp) ,M ) + operate.multiply(operate.multiply(M , temp),operate.index((1 - temp),(M-1))) - temp)
        return border_values
    
    def solve_equation(self, f, max_iter=100, tol=1e-6):
        """
        数值求解方程 f(M) = 0
        使用二分法求解
        """
        # 确定搜索范围
        low, high = 1, 10000
        
        # 二分法求解
        for _ in range(max_iter):
            mid = operate.divide( (low + high) , 2)
            f_mid = f(mid)
            
            if abs(f_mid) < tol:
                return mid
            
            if f_mid > 0:
                low = mid
            else:
                high = mid
        
        return operate.divide( (low + high) , 2)
    
    def estimate_tag_count(self, frame_size, N_Idle, N_Success):
        """
        估计标签数量范围
        根据论文算法3.2
        N_Idle:空闲时隙数, 
        N_Success:成功识别时隙数
        """  
        #空闲时隙比例(1-1/frame_size)^M
        if frame_size > 0:
            eta_I = operate.divide( N_Idle , frame_size)
        else:
            eta_I =  0

        # 情况1: 存在空闲时隙
        if eta_I > 0:
            # 找到最接近的分界点
             # 利用公式估计M = round(-frame_size * log(eta_I))
            if eta_I >= 1.0:
                M_est = 0
            else:
                M_est = round(operate.divide(math.log(eta_I) , math.log(1 - operate.divide(1,frame_size))))
            # 再加上成功时隙数量，按论文建议
            M_est += N_Success
            return M_est, self.find_optimal_frame_size(M_est)
        
        # 情况2: 没有空闲时隙但有成功时隙
        elif N_Idle == 0 and N_Success > 0:
            # 边界：全部无空闲但有成功，说明标签数逼近M_{idle}^{border}
            M_est = int(self.border_values.get((frame_size, 'idle'), 50))
            return M_est, self.find_optimal_frame_size(M_est)
        else:
            # 完全无空闲/无成功，按collision边界
            M_est = int(self.border_values.get((frame_size, 'collision'), 100))
            return M_est, self.find_optimal_frame_size(M_est)
    
    def find_optimal_frame_size(self, M_est):
        """
        根据估计的标签数量找到最优帧大小
        根据论文表3的映射关系
        """
        # 找到最接近的帧大小
        """查找M_est所在区间，输出对应帧长"""
        for low, high, frame_size in self.frame_intervals:
            if low <= M_est <= high:
                return frame_size
        # 如果不在任何范围内，返回最大帧大小
        return self.FRAME_SIZES[-1]

    def manage_collision(self, tags):
        """
        处理碰撞并完成标签识别
        返回使用的总时隙数
        """
        self.reset_stats()
        # 在帧时隙ALOHA中，我们一次处理整个帧
        # 注意：这里我们假设一次manage_collision调用处理一帧
        # 创建活跃标签列表
        active_tags = [tag for tag in tags if tag.active] 

        while active_tags:
            # 处理当前一帧
            N_Idle, N_Success, N_Collision = self.frame_process(active_tags)
            self.total_slots += self.frame_size
            self.frame_count += 1
            
            # 根据当前帧结果估计标签数量并调整帧大小
            M_est, next_frame_size = self.estimate_tag_count(self.frame_size, N_Idle, N_Success)
            self.adjust_frame_size(next_frame_size)

            # 更新活跃标签列表（只包含仍活跃的标签）
            active_tags = [tag for tag in active_tags if tag.active]
            #需要继续写和理解
            #logger.info(f"frame_count:{self.frame_count}\tframe_size:{self.frame_size}")
        return self.total_slots #返回使用的总时隙数return self.run_frame(tags)
    #添加返回当前帧的统计信息(空闲时隙数、成功时隙数、碰撞时隙数)
    #一次处理一帧，并调整帧长
    def frame_process(self , activetags):
        frame_empty, frame_success, frame_collision = 0, 0, 0
        
        for tag in activetags:#处于活跃的标签选择时隙
            tag.select_slot(self.frame_size)

        #初始化时隙数组，将在同一个时隙的标签统计出来
        slots = [[] for _ in range(self.frame_size)]
        for tag in activetags:
            slots[tag.selected_slot].append(tag)

        #处理每个时隙
        for slot in slots:
            num_tags = len(slot)

            if num_tags == 0:  #此时隙无标签，即该时隙为空闲
                frame_empty += 1
                self.empty_slot_count+=1
            
            elif num_tags == 1:#此时隙1个标签，该时隙标签可成功识别
                #成功识别
                tag = slot[0]
                tag.mark_success()
                self.success_count += 1
                frame_success += 1

            else:                       #此时隙>1个标签，该时隙标签出现碰撞
                frame_collision += 1
                self.collision_count += 1 
                
                #for tag in tags_in_slot:
                #    tag.handle_collision()

        return frame_empty , frame_success , frame_collision

    def adjust_frame_size(self, new_size):
        """调整帧大小（时隙数量）"""
        # 找到最接近的预定义帧大小
        #min:寻找列表中最小值，第二个元素表示如何决定评估元素的大小
        closest = min(self.FRAME_SIZES, key=lambda x: abs(x - new_size))
        self.frame_size = closest
        
    def get_stats(self):
        """获取统计信息"""
        return {
            "total_slots": self.total_slots,
            "success_count": self.success_count,
            "collision_count": self.collision_count,
            "empty_slot_count": self.empty_slot_count,
            "frame_count": self.frame_count,
            "current_frame_size": self.frame_size,
            "efficiency": self.success_count / self.total_slots if self.total_slots > 0 else 0
        }
    
    def reset_stats(self):
        """重置统计计数器"""
        self.total_slots = 0
        self.success_count = 0
        self.collision_count = 0
        self.empty_slot_count = 0
        self.frame_count = 0

   
class DTS_DFSATagReader():
    def __init__(self,initial_frame_size=16):
        super().__init__()
        operate.reset_stats()
        self.MIN_FRAME_SIZE = 4
        self.MAX_FRAME_SIZE = 2048
        self.frame_size = initial_frame_size
        self.CR_HIGH = 5  # 代表0.7
        self.CR_LOW = 4   # 代表0.3
        self.reset_stats()

    def manage_collision(self, tags):

        self.reset_stats()
        active_tags = [tag for tag in tags if tag.active]
        while active_tags:
            n_idle, n_success, n_collision = self.frame_process(active_tags)
            self.total_slots += self.frame_size
            self.frame_count += 1
            
            cr =   operate.divide(operate.multiply(n_collision,10) , self.frame_size )   # 0~10，整数化碰撞比例,DTS-DFSA：帧长调整（整数版）
            if cr > self.CR_HIGH:
                self.frame_size = min(operate.bit_shift(self.frame_size , "left"  , 1) , self.MAX_FRAME_SIZE)  # 左移×2
            elif cr < self.CR_LOW:
                self.frame_size = max(operate.bit_shift(self.frame_size , "right" , 1) , self.MIN_FRAME_SIZE)  # 右移÷2

            active_tags = [tag for tag in active_tags if tag.active]
        return self.total_slots

    #添加返回当前帧的统计信息(空闲时隙数、成功时隙数、碰撞时隙数)
    #一次处理一帧，并调整帧长
    def frame_process(self , activetags):
        frame_empty, frame_success, frame_collision = 0, 0, 0
        
        for tag in activetags:#处于活跃的标签选择时隙
            tag.select_slot(self.frame_size)

        #初始化时隙数组，将在同一个时隙的标签统计出来
        slots = [[] for _ in range(self.frame_size)]
        for tag in activetags:
            slots[tag.selected_slot].append(tag)

        #处理每个时隙
        for slot in slots:
            num_tags = len(slot)

            if num_tags == 0:  #此时隙无标签，即该时隙为空闲
                frame_empty += 1
                self.empty_slot_count+=1
            
            elif num_tags == 1:#此时隙1个标签，该时隙标签可成功识别
                #成功识别
                tag = slot[0]
                tag.mark_success()
                self.success_count += 1
                frame_success += 1

            else:                       #此时隙>1个标签，该时隙标签出现碰撞
                frame_collision += 1
                self.collision_count += 1 
                
                #for tag in tags_in_slot:
                #    tag.handle_collision()

        return frame_empty , frame_success , frame_collision

    def reset_stats(self):
        """重置统计计数器"""
        self.total_slots = 0
        self.success_count = 0
        self.collision_count = 0
        self.empty_slot_count = 0
        self.frame_count = 0
